#include <stdio.h>
#include <stdlib.h>
#include "dfa.h"

void addState(DFA* dfa, DFAState newState) {
    
    /* add storage*/
    dfa->statesNum++;
    dfa->states = (DFAState*)realloc(dfa->states, sizeof(DFAState)*dfa->statesNum);
    
    /* add new state*/
    dfa->states[dfa->statesNum-1].nfaStateIndices = newState.nfaStateIndices;
    dfa->states[dfa->statesNum-1].nfaStatesNum = newState.nfaStatesNum;
    
    return;
    
}

void addTransition(DFA* dfa, int srcStateIndex, int symbolIndex, int dstStateIndex) {
    
    /* add storage */
    dfa->transTblSize++;
    dfa->transTbl = (Transition*)realloc(dfa->transTbl, sizeof(Transition)*dfa->transTblSize);
    
    /* add Transition */
    dfa->transTbl[dfa->transTblSize-1].source = srcStateIndex;
    dfa->transTbl[dfa->transTblSize-1].symbol = symbolIndex;
    dfa->transTbl[dfa->transTblSize-1].destination = dstStateIndex;
    
    return;
    
}

int pow2(int exponent) {
    
    int i, product = 1;
    
    for (i = 0; i < exponent; i++) {
        product *= 2;
    }
    
    return product;

}

void setID(DFAState* dfaState) {
    
    int i, sum;
    
    sum = 0;
    
    for (i = 0; i < dfaState->nfaStatesNum; i++) {
        sum += pow2( dfaState->nfaStateIndices[i] );
    }
    
    dfaState->id = sum;

    return;
    
}

/* returns index of dfaState in dfa->states if exists */
int searchDFAState(DFA* dfa, DFAState dfaState) {
    
    int i, indexFound;
    indexFound = 0;
    
    for (i = 0; i < dfa->statesNum; i++) {
        if (dfa->states[i].id == dfaState.id) {
            indexFound = i;
        }
    }
    
    return indexFound;

}

void labelDFAFinalStates(DFA* dfa) {
    
    int i,j,k,isFinal;
    
    dfa->finalStatesNum = 0;
    
    for (i = 0; i < dfa->statesNum; i++) {
        
        isFinal = 0;
        
        for (j = 0; j < dfa->states[i].nfaStatesNum; j++) {
            for (k = 0; k < dfa->nfa->finalStatesNum; k++) {
                if (dfa->nfa->finalStatesIndices[k] == dfa->states[i].nfaStateIndices[j]) {
                    isFinal = 1;
                }
            }
        }
        
        if (isFinal) {
            dfa->finalStatesIndices[dfa->finalStatesNum] = i;
            dfa->finalStatesNum++;
        }        
        
    }
    
    return;

}

DFA* getDFAForNFA(NFA* inputNFA, NextClosureStates* inputNFANextClosures) {
    
    DFA* dfa;
    DFAStateQueue* queue;
    DFAState *state, *newState;
    
    int i,j,k,l;
    int* nextStates;
    int nfaStateIndex, stateIndex, dfaStateIndex;
    
    /* initialize DFA */
    dfa = (DFA*)malloc(sizeof(DFA));
    dfa->nfa = inputNFA;
    dfa->nfaNextClosures = inputNFANextClosures;
    dfa->states = NULL;
    dfa->statesNum = 0;
    dfa->transTbl = NULL;
    dfa->transTblSize = 0;
    
    /* initialize Queue */
    queue = createDFAStateQueue();
    
    state = (DFAState*)malloc(sizeof(DFAState));
    state->nfaStatesNum = 1 + dfa->nfaNextClosures[dfa->nfa->initStateIndex].closureSize;
    state->nfaStateIndices = (int*)malloc(state->nfaStatesNum * sizeof(int));
    state->nfaStateIndices[0] = dfa->nfa->initStateIndex; /* add the nfa state itself */
    for (i = 1; i < state->nfaStatesNum ; i++) {
        state->nfaStateIndices[i] = dfa->nfaNextClosures[dfa->nfa->initStateIndex].closureStates[i];
    }
    setID(state);

    /* add initial state to queue */
    enQueue(queue, state);
    
    nextStates = (int*)calloc(dfa->nfa->statesNum, sizeof(int));
    
    while (isEmpty(queue) == 0) {
        
        state = deQueue(queue);
        
        /* traverse through all symbol transitions */
        for (i = 0; i < dfa->nfa->alphabetSize; i++) {
            
            /* if epsilon then skip */
            if (i == dfa->nfa->epsilonIndex) {
                continue;
            }
            
            /* clear previous values */
            for (j = 0; j < dfa->nfa->statesNum; j++) {
                nextStates[j] = 0;
            }
            
            /* for each nfa state */
            for (j = 0; j < state->nfaStatesNum; j++) {
                
                nfaStateIndex = state->nfaStateIndices[j];
                
                for (k = 0; k < dfa->nfaNextClosures[nfaStateIndex].nextStatesSize; k++) {
                    
                    /* check if next state on current alphabet*/
                    if (dfa->nfaNextClosures[nfaStateIndex].nextStateSymbols[k] == i) {
                        /* add state to next states */
                        nextStates[dfa->nfaNextClosures[nfaStateIndex].nextStates[k]] = 1;
                        /* also add its closure*/
                        for (l = 0; l < dfa->nfaNextClosures[dfa->nfaNextClosures[nfaStateIndex].nextStates[k]].closureSize; l++) {
                            nextStates[ dfa->nfaNextClosures[dfa->nfaNextClosures[nfaStateIndex].nextStates[k]].closureStates[l] ] = 1;
                        }
                    }
                    
                }
                
            }
            
            /* create dfa state using nfa states reached */
            newState = (DFAState*)malloc(sizeof(DFAState));
            newState->nfaStatesNum = 0;
            newState->nfaStateIndices = (int*)calloc(dfa->nfa->statesNum,sizeof(int));
            for (j = 0; j < dfa->nfa->statesNum; j++) {
                if (nextStates[j] == 1) {
                    newState->nfaStateIndices[newState->nfaStatesNum] = j;
                    newState->nfaStatesNum++;
                }                
            }
            newState->nfaStateIndices = (int*)realloc(newState->nfaStateIndices, sizeof(int)*newState->nfaStatesNum); /* resizing */
            setID(newState);
            
            /* get indices in dfa->states array */
            stateIndex = searchDFAState(dfa, *state);
            dfaStateIndex = searchDFAState(dfa, *newState);
            
            if (dfaStateIndex) {
                /* add transition */
                addTransition(dfa, stateIndex, i, dfaStateIndex);
                free(newState);
            } else {
                addState(dfa, *newState);
                addTransition(dfa, stateIndex, i, (dfa->statesNum-1) ); /* index of last state added */
                enQueue(queue, newState);
            }
            
        }

        free(state);
        
    }
    
    free(nextStates);
    
    /* add final states */
    labelDFAFinalStates(dfa);
    
    return dfa;
    
}

void printDFA(DFA* dfa) {
    
    int i,j;
    
    printf("The states of the DFA in terms of that of nfa are :\n");
    
    for (i = 0; i < dfa->statesNum; i++) {
        printf("d%d\t:\t",i);
        for (j = 0; j < dfa->states[i].nfaStatesNum; j++) {
            printf("%s,",dfa->nfa->states[dfa->states[i].nfaStateIndices[j]]);
        }
        printf("\n");
    }
    
    printf("\nInitial State is d%d\n",dfa->initStateIndex);
    
    printf("\nFinal States are : ",dfa->initStateIndex);
    for (i = 0; i < dfa->finalStatesNum; i++) {
        printf("d%d,",dfa->finalStatesIndices[i]);
    }
    printf("\n");
    
    printf("\nThe Transitions of DFA are: \n");
    for (i = 0; i < dfa->transTblSize; i++) {
        printf("(d%d, %s, d%d)\n",dfa->transTbl[i].source, dfa->nfa->alphabet[dfa->transTbl[i].symbol], dfa->transTbl[i].destination);
    }
    

    
}

/* Queue methods */

DFAStateQueue* createDFAStateQueue(void) {
    
    DFAStateQueue* queue;
    
    queue = (DFAStateQueue*)malloc(sizeof(DFAStateQueue));
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
    
    return queue;
    
}

int isEmpty(DFAStateQueue* dfaStateQueue) {
    
    if ((dfaStateQueue->front == NULL) && (dfaStateQueue->rear == NULL)) {
        return 1;
    } else {
        return 0;
    }
    
}

void enQueue(DFAStateQueue* dfaStateQueue, DFAState* dfaState) {
    
    DFAStateQueueElement* newElement;
    
    newElement = (DFAStateQueueElement*)malloc(sizeof(DFAStateQueueElement));
    newElement->state = dfaState;
    newElement->next = NULL;
    
    if ((dfaStateQueue->front == NULL) && (dfaStateQueue->rear == NULL)) {
        dfaStateQueue->front = newElement;
        dfaStateQueue->rear = newElement;
    } else {
        dfaStateQueue->rear->next = newElement;
        dfaStateQueue->rear = newElement;
    }
    dfaStateQueue->size += 1;
    
    return;
    
}

DFAState* deQueue(DFAStateQueue* dfaStateQueue) {
    
    DFAStateQueueElement* removedElement;
    DFAState* state;
    
    if (isEmpty(dfaStateQueue)) {
        removedElement = NULL;
    } else {
        removedElement = dfaStateQueue->front;
        dfaStateQueue->front = dfaStateQueue->front->next;
    }
    dfaStateQueue->size -= 1;
    
    /* clear rear if empty */
    if (dfaStateQueue->size == 0) {
        dfaStateQueue->rear = NULL;
    }
    
    /* free removed element */
    removedElement->next = NULL;
    state = removedElement->state;
    free(removedElement);
    
    return state;
    
}
